/*
 *时间复杂度 O(n^1.3)
 *空间复杂度 O(1)
 *算法描述
	先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
	（1）选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
	（2）按增量序列个数k，对序列进行k 趟排序；
	（3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度
 */

function shellSort(nums) {
	let len = nums.length;
	for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
		// 多个分组交替执行
		for (let i = gap; i < len; i++) {
			let j = i;
			let current = nums[i];
			while (j - gap >= 0 && current < nums[j - gap]) {
				nums[j] = nums[j - gap];
				j = j - gap;
			}
			nums[j] = current;
		}
	}
	return nums;
}
const nums = [3, 4, 5, 7, 3, 5, 8]
shellSort(nums)